package Sort.insertSort;

/**
 * 虽然插入排序仍然需要O(N^2)的时间，但是在一般情况下，要比冒泡排序快一倍，比选择排序还要快一点，
 */



/**
 * @program: jvm
 * @description
 * @author: tkk fendoukaoziji
 * @create: 2019-05-05 09:51
 **/
public class ArrayIns {
    private long[] a;
    private int nElems;

    public ArrayIns(int max){
        a=new long[max];
        nElems=0;
    }
    public void insert(long value){
        a[nElems]=value;
        nElems++;
    }

    public void display(){
        for (int j = 0; j < nElems; j++) {
            System.out.print(a[j]+" ");
        }
        System.out.println(" ");
    }


    public void insertSort(){
        int in,out;
        for ( out = 1; out <nElems ; out++) {  //out is dividing line
            long temp=a[out];   //remove marked item
            in=out;                  //start shifts at out
            while (in>0&&a[in-1]>=temp){ // until one is smaller
                a[in]=a[in-1];      //shift item to right
                --in;            //go left one position
            }
            a[in]=temp;            //insert marked item
        } //end for
    } //end insertSort
}





















